#include "gx_lsq.h"
#include "gx_err.h"
#include "gx_threadpool.h"
#include "gtest/gtest.h"
#include "gx_sort.h"
using std::endl;

TEST(lsq_test,testinit)
{
	
	LIST *list = list_new();
	ASSERT_NE((LIST*)NULL,list);
	ASSERT_EQ(0,list->count);
	ASSERT_EQ(NULL,list->head);
	ASSERT_EQ(NULL,list->tail);
	list_removeall(list,NULL);
}



TEST(lsq_test,test_addtail)
{
	
	LIST* list = list_new();
	int times = 0;
	int count = 0;
	while(times++ < 10)
	{
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)times));
		count++;
		ASSERT_EQ(count,list->count);
	}

	times = 0;

	NODE* tmp = list->head;
	while(times++ < 10)
	{
		ASSERT_EQ(times,(int)tmp->data)<<"times:"<<times;
		tmp = tmp->next;
	}

	list_removeall(list,NULL);
//	ASSERT_EQ(0,list->count);
//	ASSERT_EQ(0,list->head);
//	ASSERT_EQ(0,list->tail);
}

TEST(lsq_test,test_addhead)
{
	
	LIST* list = list_new();
	int times=0;
	int count=0;

	while(times++ < 10)
	{
		ASSERT_EQ(SUCCESS,list_addhead(list,(DATA)times));
		count++;
		ASSERT_EQ(count,list->count);
	}

	NODE* tmp = list->head;
	while(--times >0)
	{
		ASSERT_EQ(times,(int)tmp->data)<<"times:"<<times;
		tmp=tmp->next;
	}
	list_removeall(list,NULL);
}

TEST(lsq_test,testremoveall)
{
	LIST* list = list_new();
	int times =0;
	int count = 0;
	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list->count);
	}

	times = 0;

	NODE* node = list->head;
	while(times++<10)
	{
		ASSERT_EQ(times,*((int*)node->data));
		node=node->next;
	}
	list_removeall(list,free);
}

void add(DATA data)
{
	*(int*)data *= 2;
}

TEST(lsq_test,testwalk)
{
	LIST* list = list_new();
	int times = 0;
	int count = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list->count);

	}
	times = 0;

	NODE* node = list->head;
	list_walk(list,add);

	while(times++<10)
	{
		ASSERT_EQ(times*2,*((int*)node->data));
		node=node->next;
	}
	list_removeall(list,free);
}

TEST(lsq_test,testgethead)
{
	LIST* list = list_new();
	int times = 0;
	int count = 0;

	ASSERT_EQ((DATA)NULL,list_gethead(list));
	ASSERT_EQ((DATA)NULL,list_gethead(NULL));

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list->count);

	}

	ASSERT_EQ(1,*(int*)list_gethead(list));

	times--;
	NODE* tmp = list->tail;
	while(tmp != NULL)
	{
		ASSERT_EQ(times,*(int*)tmp->data);
		times--;
		tmp = tmp->prev;
	}

	tmp = list->head;
	times++;
	while(tmp != NULL)
	{
		ASSERT_EQ(times,*(int*)tmp->data);
		times++;
		tmp = tmp->next;
	}
	list_removeall(list,free);
}

TEST(lsq_test,removehead)
{
	LIST* list = list_new();
	int times = 0;
	int count = 0;

	ASSERT_EQ((DATA)NULL,list_gethead(list));
	ASSERT_EQ((DATA)NULL,list_gethead(NULL));

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list->count);

	}
	int *a =(int*)list_removehead(list);
	ASSERT_EQ(1,*a);
	free(a);
	ASSERT_EQ(count-1,list->count);
	ASSERT_EQ(2,*(int*)list->head->data);
	times--;
	NODE* tmp = list->tail;
	while(tmp != NULL)
	{
		ASSERT_EQ(times,*(int*)tmp->data);
		times--;
		tmp = tmp->prev;
	}

	tmp = list->head;
	times++;
	while(tmp != NULL)
	{
		ASSERT_EQ(times,*(int*)tmp->data);
		times++;
		tmp = tmp->next;
	}
	list_removeall(list,free);
}

TEST(lsq_test,pointer)
{
	LIST* list = list_new();
	int times = 0;
	int count = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list->count);

	}

	times--;
	NODE* tmp = list->tail;
	while(tmp != NULL)
	{
		ASSERT_EQ(times,*(int*)tmp->data);
		times--;
		tmp = tmp->prev;
	}

	tmp = list->head;
	times++;
	while(tmp != NULL)
	{
		ASSERT_EQ(times,*(int*)tmp->data);
		times++;
		tmp = tmp->next;
	}
	list_removeall(list,free);
}

TEST(lsq_test,get_removetail)
{
	LIST* list = list_new();
	int times = 0;
	int count = 0;

	ASSERT_EQ((DATA)NULL,list_gettail(list));
	ASSERT_EQ((DATA)NULL,list_gettail(NULL));
	ASSERT_EQ((DATA)NULL,list_removetail(list));
	ASSERT_EQ((DATA)NULL,list_removetail(NULL));

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list->count);

	}
	ASSERT_EQ(10,*(int*)list_gettail(list));
	int *a = (int*)list_removetail(list);
	ASSERT_EQ(10,*a);
	free(a);
	ASSERT_EQ(9,list->count);

	NODE *tmp = list->tail;
	times = 9;

	while(tmp != NULL)
	{
		ASSERT_EQ(times,*(int*)tmp->data);
		tmp = tmp->next;
		times--;
	}

	tmp = list->head;
	times = 1;

	while(tmp != NULL)
	{
		ASSERT_EQ(times,*(int*)tmp->data);
		tmp = tmp->next;
		times++;
	}
	list_removeall(list,free);
}

TEST(lsq_test,tail_all)
{
	LIST* list = list_new();
	int times = 0;
	int count = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list->count);

	}
	times = 0;
	count = 10;

	while(times++ < 10)
	{
		int *a = (int*)list_gettail(list);
		ASSERT_EQ(count,*a);
		a = (int*)list_removetail(list);
		ASSERT_EQ(count,*a);
		ASSERT_EQ(count-1,list->count);

		NODE* tmp = list->tail;
		int test = *a-1;
		while(tmp != NULL)
		{
			ASSERT_EQ(test,*(int*)tmp->data);
			test--;
			tmp=tmp->prev;
		}

		tmp = list->head;
		//printf("list->head:%d\n",*(int*)tmp->data);
		test = 1;
		while(tmp != NULL)
		{
			ASSERT_EQ(test,*(int*)tmp->data)<<"times"<<times;
			test++;
			tmp = tmp->next;
		}
		free(a);
		count--;
	}
	list_removeall(list,free);
}

TEST(lsq_test,head_all)
{
	LIST* list = list_new();
	int times = 0;
	int count = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list->count);

	}

	times = 0;
	count = 1;
	int num = 9;

	while(times++ < 10)
	{
		int *a = (int*)list_gethead(list);
		ASSERT_EQ(count,*a);
		a = (int*)list_removehead(list);
		ASSERT_EQ(*a,count);
		ASSERT_EQ(num,list->count);
		count++;
		num--;

		NODE* node = list->head;
		int test = *a+1;
		while(node != NULL)
		{
			ASSERT_EQ(test,*(int*)node->data);
			test++;
			node=node->next;
		}

		node = list->tail;
		test = 10;
		while(node != NULL)
		{
			ASSERT_EQ(test,*(int*)node->data);
			test++;
			node=node->next;
		}
		free(a);
	}
	list_removeall(list,free);
}

int compare(DATA d1,DATA d2)
{
	int a = *(int*)d1;
	int b = *(int*)d2;
	return a-b;
}

int compareless(DATA d1,DATA d2)
{
	int a = *(int*)d1;
	int b = *(int*)d2;
	return b-a;
}

TEST(test_lsq,test_addbefore)
{
	LIST *list = list_new();

	ASSERT_EQ(PARAMETER_ERROR,list_addbefore(NULL,(DATA)(int*)1,(DATA)1,compare));
	ASSERT_EQ(NODATA,list_addbefore(list,(DATA)NULL,(DATA)1,compare));
	ASSERT_EQ(NODATA,list_addbefore(list,(DATA)1,(DATA)NULL,compare));
	ASSERT_EQ(PARAMETER_ERROR,list_addbefore(list,(DATA)1,(DATA)1,NULL));
	
	int times = 0;
	int count = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list_count(list));
	}

	int *a = (int*)malloc(sizeof(int));
	int *b = (int*)malloc(sizeof(int));
	*a = 1;
	*b = 0;
	ASSERT_EQ(SUCCESS,list_addbefore(list,a,b,compare));
	ASSERT_EQ(11,list_count(list));

	NODE *node = list->head;
	times = 0;

	ASSERT_EQ(0,*(int*)list->head->data);
	ASSERT_EQ(10,*(int*)list->tail->data);
	while(node != NULL)
	{
		ASSERT_EQ(times,*(int*)node->data);
		times++;
		node = node->next;
	}
	

	node = list->tail;
	times = 10;
	while(node != NULL)
	{
		ASSERT_EQ(times,*(int*)node->data);
		times--;
		node = node->prev;
	}

	int *c = (int*)malloc(sizeof(int));
	*c = 12;
	
	ASSERT_EQ(0,*(int*)list->head->data);
	ASSERT_EQ(SUCCESS,list_addtail(list,DATA(c)));
	ASSERT_EQ(12,list_count(list));
	ASSERT_EQ(12,*(int*)list->tail->data);

	int *d = (int*)malloc(sizeof(int));
	*d = 11;
	ASSERT_EQ(SUCCESS,list_addbefore(list,c,d,compare));
	ASSERT_EQ(13,list_count(list));
	ASSERT_EQ(12,*(int*)list->tail->data);
	
	node = list->head;
	times = 0;
	while(node != NULL)
	{
		EXPECT_EQ(times,*(int*)node->data);
		times++;
		node = node->next;
	}
	
	
	

	node = list->tail;
	times = 12;
	while(node != NULL)
	{
		ASSERT_EQ(times,*(int*)node->data);
		times--;
		node = node->prev;
	}
	
	free(a);
	list_removeall(list,free);
}

TEST(test_lsq,test_middle)
{
	LIST *list = list_new();

	int times = 0;
	int count = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list_count(list));
	}

	times = 11;
	while(times++ < 20)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list_count(list));

	}

	int *a = (int*) malloc(sizeof(int));
	int *b = (int*) malloc(sizeof(int));
	*a = 12;
	*b = 11;
	ASSERT_EQ(SUCCESS,list_addbefore(list,a,b,compare));
	ASSERT_EQ(20,list_count(list));
	free(a);
	NODE *node;
	node = list->head;
	times = 1;

	while(node != NULL)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node= node->next;
		times++;
	}
	list_removeall(list,free);
}

TEST(lsq_test,addbefore_one)
{
	LIST *list = list_new();
	int *a = (int*)malloc(sizeof(int));
	*a = 2;
	list_addtail(list,a);
	ASSERT_EQ(NULL,list->head->next);
	ASSERT_EQ(NULL,list->head->prev);
	ASSERT_EQ(2,*(int*)list->head->data);
	ASSERT_EQ(NULL,list->tail->next);
	ASSERT_EQ(NULL,list->tail->prev);
	int *b = (int*)malloc(sizeof(int));
	*b = 1;
	list_addbefore(list,a,b,compare);
	ASSERT_EQ(NULL,list->head->prev);
	ASSERT_EQ(NULL,list->tail->next);
	NODE* node = list->head;
	int times = 1;
	while(node!=NULL)
	{

		ASSERT_EQ(times,*(int*)node->data);
		node = node->next;
		times++;
	}
	list_removeall(list,free);
}



TEST(lsq_test,addbefore_all)
{
	LIST *list = list_new();

	int times = 2;
	int count = 0;

	while(times <= 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
		count++;
		ASSERT_EQ(count,list_count(list));
		times = (count+1)*2;
	}

	NODE *node = list->head;
	times =2;
	int use = 0;
	while(node != NULL)
	{
		//printf("node:%d\n",*(int*)node->data);
		ASSERT_EQ(times,*(int*)node->data);
		use++;
		times = (use+1)*2;
		node=node->next;
	}

	times = 1;
	int tmp = 0;
	int *find = (int*)malloc(sizeof(int));
	*find = 2;

	while(times <= 9)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addbefore(list,find,(DATA)a,compare));
		count++;
		tmp++;
		ASSERT_EQ(count,list_count(list));
		times = tmp*2+1;
		*find = (tmp+1)*2;
	}
	free(find);

	node = list->head;
	times = 1;
	while(node != NULL)
	{
		//printf("gaoxin:%d\n",*(int*)node->data);
		EXPECT_EQ(times,*(int*)node->data);
		node = node->next;
		times++;
	}
	node = list->tail;
	times=10;
	while(node != NULL)
	{
		EXPECT_EQ(times,*(int*)node->data);
		node = node->prev;
		times--;
	}
	list_removeall(list,free);
}

TEST(lsq_test,test_fail_add_before)
{
	LIST *list = list_new();
	int times = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
	}
	times = 10;
	while(times++ < 20)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(NODATA,list_addbefore(list,(DATA)a,(DATA)a,compare));
		free(a);
	}
	list_removeall(list,free);
}

TEST(lsq_test,listaddafterfail)
{
	LIST *list = list_new();
	ASSERT_EQ(PARAMETER_ERROR,list_addafter(NULL,(DATA)1,(DATA)1,compare));
	ASSERT_EQ(PARAMETER_ERROR,list_addafter(list,(DATA)1,(DATA)1,NULL));
	ASSERT_EQ(NODATA,list_addafter(list,NULL,(DATA)1,compare));
	ASSERT_EQ(NODATA,list_addafter(list,(DATA)1,NULL,compare));
	list_removeall(list,free);
}

TEST(lsq_test,listaddafterhead)
{
	LIST *list = list_new();
	int times = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
	}
	int *a = (int*)malloc(sizeof(int));
	*a = 0;
	int *b = (int*)malloc(sizeof(int));
	*b = 1;
	ASSERT_EQ(SUCCESS,list_addafter(list,(DATA)b,(DATA)a,compare));
	ASSERT_EQ(11,list_count(list));
	NODE* node = list->head;
	ASSERT_EQ(1,*(int*)node->data);
	node = node->next;
	ASSERT_EQ(0,*(int*)node->data);
	times = 1;
	node = node->next;
	while(times++ < 10)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node = node->next;
	}

	node = list->tail;
	times = 11;
	while(times-- > 2)
	{
	//	fprintf(stderr,"node:%d\n",*(int*)node->data);
		EXPECT_EQ(times,*(int*)node->data);
		node = node->prev;
	}
	EXPECT_EQ(0,*(int*)node->data);
	node = node->prev;
	//EXPECT_EQ(1,*(int*)node->data);
	list_removeall(list,free);

	free(b);
}

TEST(lsq_test,listaddaftertail)
{
	LIST *list = list_new();
	int times = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		ASSERT_NE((int*)NULL,a);
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,(DATA)a));
	}

	int *a = (int*) malloc(sizeof(int));
	*a = 10;
	int *b = (int*) malloc(sizeof(int));
	*b = 11;
	ASSERT_EQ(SUCCESS,list_addafter(list,a,b,compare));
	ASSERT_EQ(11,list_count(list));
	times = 0;
	NODE *node = list->head;
	while(times++ < 11)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node=node->next;
	}
	node = list->tail;
	times =11;
	while(node != NULL)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node = node->prev;
		times--;
	}
	ASSERT_EQ(0,times);
	list_removeall(list,free);
	free(a);
}

TEST(lsq_test,listaddaftermiddle)
{
	LIST *list = list_new();
	int times = 0;

	while(times++<10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,a));
	}
	times=11;
	while(times++<20)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,list_addtail(list,a));
	}
	int *a = (int*)malloc(sizeof(int));
	*a =10;
	int *b = (int*)malloc(sizeof(int));
	*b = 11;
	ASSERT_EQ(SUCCESS,list_addafter(list,a,b,compare));
	ASSERT_EQ(20,list_count(list));
	times=1;
	NODE *node = list->head;
	while(node != NULL)
	{
		ASSERT_EQ(times,*(int*)node->data);
		times++;
		node = node->next;
	}
	ASSERT_EQ(21,times);
	node = list->tail;
	times = 20;
	while(node != NULL)
	{
		ASSERT_EQ(times,*(int*)node->data);
		times--;
		node = node->prev;
	}
	ASSERT_EQ(0,times);
	list_removeall(list,free);
	free(a);
}

TEST(test_lsq,listaddafterone)
{
	LIST *list = list_new();
	int *a = (int*)malloc(sizeof(int));
	*a =1;
	int *b = (int*)malloc(sizeof(int));
	*b = 2;
	list_addtail(list,a);
	list_addafter(list,a,b,compare);
	ASSERT_EQ(2,list_count(list));
	NODE *node = list->head;
	ASSERT_EQ(1,*(int*)node->data);
	node = node->next;
	ASSERT_EQ(2,*(int*)node->data);
	node = list->tail;
	ASSERT_EQ(2,*(int*)node->data);
	node = node->prev;
	ASSERT_EQ(1,*(int*)node->data);
	list_removeall(list,free);
}

TEST(test_lsq,listaddafterall)
{
	
	LIST *list = list_new();
	int times = 1;
	int count = 1;
	while(times <= 9)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
		times = count*2+1;
		count++;
	}
	
	
	ASSERT_EQ(5,list_count(list));

	times = 2;
	count = 1;
	int *find =(int*)malloc(sizeof(int));
	*find = 1;
	while(times <= 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,list_addafter(list,find,a,compare));
		times = (count+1)*2;
		*find = count*2+1;
		count++;
	}
	
	
	ASSERT_EQ(10,list_count(list));
	NODE *node = list->head;
	times = 1;
	while(node != NULL)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node = node->next;
		times++;
	}
	node = list->tail;
	times = 10;
	while(node != NULL)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node= node->prev;
		times--;
	}
	list_removeall(list,free);
	free(find);
	
}

TEST(test_lsq,listaddafterfail)
{
	LIST* list = list_new();
	int times =0;
	while(times++ < 10)
	{
		int *a = (int *)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
	}
	int *b = (int*)malloc(sizeof(int));
	*b = 20;
	while(times++ < 10)
	{
		ASSERT_EQ(NODATA,list_addafter(list,b,DATA(1),compare));
	}
	list_removeall(list,free);
	free(b);
}

TEST(test_lsq,listisexistparameter)
{
	LIST *list = list_new();
	ASSERT_EQ(NODATA,list_isexist(list,(DATA)1,compare));
	ASSERT_EQ(NODATA,list_isexist(NULL,(DATA)1,compare));
	ASSERT_EQ(NODATA,list_isexist(list,NULL,compare));
	ASSERT_EQ(PARAMETER_ERROR,list_isexist(list,(DATA)1,NULL));
	list_removeall(list,NULL);
}

TEST(test_lsq,listisexisttrue)
{
	LIST *list = list_new();
	int times = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
	}
	
	times = 0;
	int *a = (int*)malloc(sizeof(int));
	while(times++ < 10)
	{
		*a = times;
		ASSERT_EQ(SUCCESS,list_isexist(list,a,compare));
	}

	free(a);
	list_removeall(list,free);
}

TEST(test_lsq,listisexistfailure)
{
	LIST *list = list_new();
	int times = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
	}
	int *a = (int*)malloc(sizeof(int));
	*a = 11;
	ASSERT_EQ(NODATA,list_isexist(list,a,compare));
	list_removeall(list,free);
	free(a);
}

TEST(test_lsq,listfinddataparameter)
{
	LIST* list = list_new();
	ASSERT_EQ(NULL,list_finddata(NULL,(DATA)1,compare));
	ASSERT_EQ(NULL,list_finddata(list,NULL,compare));
	ASSERT_EQ(NULL,list_finddata(list,(DATA)1,NULL));
	list_removeall(list,free);
}

TEST(test_lsq,listfinddatasuccess)
{
	LIST *list = list_new();
	int times = 0;
	while(times++<10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
	}
	times = 0;

	int *b =(int*)malloc(sizeof(int));
	while(times++ < 10)
	{
		*b = times;
		NODE *node = list_finddata(list,b,compare);
		ASSERT_EQ(times,*(int*)node->data);
	}
	free(b);
	list_removeall(list,free);
}

TEST(test_lsq,listfinddatafailure)
{
	LIST *list = list_new();
	int times = 0;
	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
	}
	int *b = (int*)malloc(sizeof(int));
	*b = 20;
	while(times++ < 10)
	{
		ASSERT_EQ(NULL,list_finddata(list,b,compare));
	}
	free(b);
	list_removeall(list,free);
}

TEST(test_lsq,listremovedataparameter)
{
	LIST* list = list_new();
	ASSERT_EQ(NULL,list_removedata(NULL,(DATA)1,compare));
	ASSERT_EQ(NULL,list_removedata(list,NULL,compare));
	ASSERT_EQ(NULL,list_removedata(list,(DATA)1,NULL));
	list_removeall(list,free);
}

TEST(test_lsq,listremovedatahead)
{
	LIST *list = list_new();
	int times = 0;

	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
	}
	
	int *c = (int*)malloc(sizeof(int));
	*c =1;
	int *b = (int*)list_removedata(list,c,compare);
	
	ASSERT_EQ(*b,1);
	ASSERT_EQ(9,list_count(list));
	NODE *node = list->head;
	times = 1;
	while(times++ < 10)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node = node->next;
	}
	ASSERT_EQ(11,times);
	ASSERT_EQ(NULL,node);
	node = list->tail;
	times = 11;
	while(times-- > 2)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node = node->prev;
	}
	ASSERT_EQ(NULL,node);
	ASSERT_EQ(1,times);
	list_removeall(list,free);
	free(c);
	free(b);
}

TEST(test_lsq,listremovedatatail)
{
	LIST *list = list_new();
	int times = 0;
	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
	}
	int *c = (int*)malloc(sizeof(int));
	*c = 10;
	int *b = (int*)list_removedata(list,c,compare);
	ASSERT_EQ(*b,10);
	ASSERT_EQ(9,list_count(list));
	times = 0;
	NODE *node = list->head;
	while(times++ < 9)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node = node->next;
	}
	ASSERT_EQ(10,times);
	ASSERT_EQ(NULL,node);
	times = 10;
	node = list->tail;
	while(times-- > 1)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node = node->prev;
	}
	ASSERT_EQ(0,times);
	ASSERT_EQ(NULL,node);
	list_removeall(list,free);
	free(c);
	free(b);
}

TEST(test_lsq,listremovedatamiddle)
{
	LIST *list = list_new();
	int times = 0;
	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
	}
	int *c = (int*)malloc(sizeof(int));
	*c = 5;
	int *b =(int*)list_removedata(list,c,compare);
	ASSERT_EQ(*b,5);
	ASSERT_EQ(9,list_count(list));
	NODE *node = list->head;
	times = 0;
	while(times++ < 4)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node = node->next;
	}
	ASSERT_EQ(5,times);
	//node = node->next;
	while(times++ < 10)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node = node->next;
	}
	times = 11;
	node = list->tail;
	while(times-- > 6)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node = node->prev;
	}
	ASSERT_EQ(5,times);
	//node = node->prev;
	while(times-- > 1)
	{
		ASSERT_EQ(times,*(int*)node->data);
		node = node->prev;
	}
	ASSERT_EQ(0,times);
	list_removeall(list,free);
	free(c);
	free(b);
}
TEST(lsq_test,listremovedatafailed)
{
	LIST* list = list_new();
	int times = 0;
	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
	}
	int *b =(int*)malloc(sizeof(int));
	*b = 20;
	ASSERT_EQ(NULL,list_removedata(list,b,compare));
	list_removeall(list,free);
	free(b);
}

TEST(lsq_test,listfirstposparameter)
{
	LIST* list = list_new();
	NODE* node;
	ASSERT_EQ(NULL,list_firstpos(NULL,&node));
	ASSERT_EQ(NULL,list_firstpos(list,NULL));
	list_removeall(list,free);
}

TEST(lsq_test,listfirstpossuccess)
{
	LIST *list = list_new();
	NODE* node = NULL;
	int times = 0;
	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
	}
	ASSERT_EQ(11,times);
	ASSERT_EQ(1,*(int*)list_firstpos(list,&node));
	ASSERT_EQ(node,list->head);
	list_removeall(list,free);
}

TEST(lsq_test,listfirstposfailure)
{
	LIST *list = list_new();
	NODE* node = NULL;
	ASSERT_EQ(NULL,list_firstpos(list,&node));
	ASSERT_EQ(NULL,node);
	list_removeall(list,free);
}
TEST(lsq_test,listnextposparameter)
{
	LIST *list = list_new();
	NODE* node = NULL;
	ASSERT_EQ(NULL,list_nextpos(NULL,&node));
	ASSERT_EQ(NULL,list_nextpos(list,NULL));
	list_removeall(list,free);
}

TEST(lsq_test,listnextpostest)
{
	LIST *list = list_new();
	int times = 0;
	while(times++ < 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		list_addtail(list,a);
	}
	NODE *node = NULL;
	int *a = (int*)list_firstpos(list,&node);
	EXPECT_EQ(1,*a);
	times = 2;
	ASSERT_EQ(NULL,list->tail->next);
	
	while(node != NULL )
	{
		//ASSERT_NE(times,11);
		a = (int*)list_nextpos(list,&node);
		if(a != NULL)
			EXPECT_EQ(times,*a);
		else
		{
			EXPECT_EQ(a,(int*)NULL);
		}
		times++;
	}
	
	list_removeall(list,free);
}

TEST(lsq_test,listempty)
{
	LIST *list = list_new();
	ASSERT_EQ(PARAMETER_ERROR,list_empty(NULL));
	ASSERT_EQ(1,list_empty(list));
	list_addtail(list,(DATA)1);
	ASSERT_EQ(0,list_empty(list));
	list_removeall(list,NULL);
}

TEST(stack_test,stacknew)
{
	STACK *stack = stack_new();
	ASSERT_NE((STACK*)NULL,stack);
	stack_freeall(stack,free);
}

TEST(stack_test,stackpushpop)
{
	STACK *stack = stack_new();
	int times = 0;
	ASSERT_EQ(1,stack_empty(stack));
	while(++times <= 10)
	{
		stack_push(stack,(DATA)times);
	}
	ASSERT_EQ(11,times);
	ASSERT_EQ(10,stack_count(stack));
	ASSERT_EQ(0,stack_empty(stack));
	times = 11;
	while(--times >= 1)
	{
		ASSERT_EQ(times,(int)stack_pop(stack));
	}
	ASSERT_EQ(0,stack_count(stack));
	ASSERT_EQ(1,stack_empty(stack));
	stack_freeall(stack,NULL);
}

TEST(test_queue,testqueueall)
{
	QUEUE *queue = queue_new();
	int times = 0;
	ASSERT_EQ(1,queue_empty(queue));

	while(++times <= 10)
	{
		ASSERT_EQ(SUCCESS,queue_in(queue,(DATA)times));
	}
	ASSERT_EQ(0,queue_empty(queue));
	ASSERT_EQ(10,queue_count(queue));
	ASSERT_EQ(11,times);
	times = 0;

	while(++times <= 10)
	{
		ASSERT_EQ(times,(int)queue_out(queue));
	}
	ASSERT_EQ(1,queue_empty(queue));
	ASSERT_EQ(0,queue_count(queue));
	queue_freeall(queue,NULL);
}

TEST(test_ltseq,ltseqnewfree)
{
	LTSEQ *ltq = ltseq_new(compare);
	list_removeall((LIST*)ltq,free);
	//ltq = ltseq_new(NULL);
}

TEST(test_ltseq,ltseqaddafter)
{
	LTSEQ *ltq = ltseq_new(compare);
	int times = 0;
	ASSERT_EQ(0,list_count((LIST*)ltq));

	while(++times <= 10)
	{
		int *a = (int *)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,ltseq_add(ltq,a));
	}

	ASSERT_EQ(times,11);
	ASSERT_EQ(10,list_count((LIST*)ltq));

	NODE *node = NULL;
	int *a = (int*)list_firstpos((LIST*)ltq,&node);
	ASSERT_EQ(1,*a);
	times = 2;

	do
	{
		a = (int*)list_nextpos((LIST*)ltq,&node);
		if(a == NULL)
			break;
		ASSERT_EQ(times,*a);
		times++;
	}while(a != NULL);
	ASSERT_EQ(times,11);

	list_removeall((LIST*)ltq,free);
}

TEST(test_ltseq,ltseqaddbefore)
{
	LTSEQ *ltq = ltseq_new(compare);
	int times = 11;

	while(--times >= 1)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,ltseq_add(ltq,a));
	}

	ASSERT_EQ(10,list_count((LIST*)ltq));
	times = 2;
	NODE *node = NULL;
	int *a = (int*)list_firstpos((LIST*)ltq,&node);
	ASSERT_EQ(1,*a);
	while((a = (int*)list_nextpos((LIST*)ltq,&node)) != NULL)
	{
		ASSERT_EQ(times,*a);
		times++;
	}
	ASSERT_EQ(times,11);
	list_removeall((LIST*)ltq,free);
}

TEST(test_ltseq,ltseqaddall1)
{
	LTSEQ *ltq = ltseq_new(compare);
	int times = 1;
	int count = 0;
	while(times <= 9)
	{
		int *a =(int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,ltseq_add(ltq,a));
		count++;
		times = count*2 +1;
	}
	ASSERT_EQ(5,list_count((LIST*)ltq));
	times = 2;
	count = 1;
	while(times <= 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,ltseq_add(ltq,a));
		count ++;
		times = count*2;
	}
	ASSERT_EQ(10,list_count((LIST*)ltq));
	times = 2;
	NODE *node = NULL;
	int *a =(int*)list_firstpos((LIST*)ltq,&node);
	ASSERT_EQ(1,*a);
	while((a = (int*)list_nextpos((LIST*)ltq,&node)) != NULL)
	{
		ASSERT_EQ(times,*a);
		times++;
	}
	ASSERT_EQ(11,times);
	list_removeall((LIST*)ltq,free);
}

TEST(test_ltseq,ltseqaddall2)
{
	LTSEQ *ltq = ltseq_new(compare);
	int times = 2;
	int count = 1;

	while(times <= 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,ltseq_add(ltq,a));
		times = ++count*2;
	}

	ASSERT_EQ(times,12);
	ASSERT_EQ(count,6);
	ASSERT_EQ(5,list_count((LIST*)ltq));

	times = 1;
	count =0;

	while(times <= 9)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,ltseq_add(ltq,a));
		times = ++count*2+1;
	}

	ASSERT_EQ(11,times);
	ASSERT_EQ(5,count);

	NODE *node;
	int *a = (int*)list_firstpos((LIST*)ltq,&node); 
	ASSERT_EQ(1,*a);
	times = 2;

	while((a =(int*)list_nextpos((LIST*)ltq,&node)) != NULL)
	{
		ASSERT_EQ(times,*a);
		times++;
	}

	ASSERT_EQ(11,times);
	list_removeall((LIST*)ltq,free);
}

TEST(test_ltseq,ltseqaddrand)
{
	int times = 10;
	int count = 20;

	while(--times >= 0)
	{
		LTSEQ *ltq = ltseq_new(compare);

		while(--count >= 0)
		{
			int *a = (int*)malloc(sizeof(int));
			*a = rand()%100;
			ASSERT_EQ(SUCCESS,ltseq_add(ltq,a));
		}

		ASSERT_EQ(20,list_count((LIST*)ltq));
		ASSERT_EQ(-1,count);
		count = 20;
		NODE *node = NULL;
		int *a = (int*)list_firstpos((LIST*)ltq,&node);
		int tmp = *a;
		while((a = (int*)list_nextpos((LIST*)ltq,&node)) != NULL)
		{
			ASSERT_LE(tmp,*a);
			tmp = *a;
			//printf("tmp:%d,",tmp);
		}
		//printf("\n");

		a = (int*)list_firstpos((LIST*)ltq,&node);
		//printf("%d,",*a);
		while((a=(int*)list_nextpos((LIST*)ltq,&node)) != NULL)
		{
		//	printf("%d,",*a);
		}
		//printf("\n");
		list_removeall((LIST*)ltq,free);
	}
}

TEST(test_ltseq,ltseqaddrandless)
{
	int times = 10;
	int count = 20;

	while(--times >= 0)
	{
		LTSEQ *ltq = ltseq_new(compareless);

		while(--count >= 0)
		{
			int *a = (int*)malloc(sizeof(int));
			*a = rand()%100;
			ASSERT_EQ(SUCCESS,ltseq_add(ltq,a));
		}

		ASSERT_EQ(20,list_count((LIST*)ltq));
		ASSERT_EQ(-1,count);
		count = 20;
		NODE *node = NULL;
		int *a = (int*)list_firstpos((LIST*)ltq,&node);
		int tmp = *a;
		while((a = (int*)list_nextpos((LIST*)ltq,&node)) != NULL)
		{
			ASSERT_GE(tmp,*a);
			tmp = *a;
		}

		a = (int*)list_firstpos((LIST*)ltq,&node);
//		printf("%d,",*a);
		while((a=(int*)list_nextpos((LIST*)ltq,&node)) != NULL)
		{
//			printf("%d,",*a);
		}
		//printf("\n");
		list_removeall((LIST*)ltq,free);
	}
}

TEST(test_ltseq,ltseqfinddataparameter)
{
	LTSEQ* ltq = ltseq_new(compare);
	ASSERT_EQ(NULL,ltseq_finddata(ltq,(DATA)1));
	ASSERT_EQ(NULL,ltseq_finddata(NULL,(DATA)1));
	ASSERT_EQ(NULL,ltseq_finddata(ltq,NULL));
	list_removeall((LIST*)ltq,free);
}

TEST(test_ltseq,ltseqfindsuccess)
{
	LTSEQ* ltq = ltseq_new(compare);
	int times = 0;

	while(++times <= 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,ltseq_add(ltq,a));
	}

	times = 0;

	while(++times <= 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		NODE *node = ltseq_finddata(ltq,a);
		ASSERT_NE((NODE*)NULL,node);
		ASSERT_EQ(*(int*)node->data,times);
		free(a);
	}
	list_removeall((LIST*)ltq,free);
}

TEST(test_ltseq,ltseqfindfailure)
{
	LTSEQ* ltq = ltseq_new(compare);
	int times = 1;
	int count = 0;

	while(times <= 9)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,ltseq_add(ltq,a));
		times = ++count*2+1;
	}

	times = 0;
	count = 0;
	while(times <= 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(NULL,ltseq_finddata(ltq,a));
		times = ++count*2;
		free(a);
	}
	list_removeall((LIST*)ltq,free);
}

TEST(test_ltseq,testlistmethod)
{
	LTSEQ *ltq = ltseq_new(compare);
	int times = 0;

	while(++times <= 10)
	{
		int *a = (int*)malloc(sizeof(int));
		*a = times;
		ASSERT_EQ(SUCCESS,ltseq_add(ltq,a));
	}
	ASSERT_EQ(1,*(int*)list_gethead((LIST*)ltq));
	ASSERT_EQ(10,*(int*)list_gettail((LIST*)ltq));
	int *a = (int*)list_removehead((LIST*)ltq);
	ASSERT_EQ(9,list_count((LIST*)ltq));
	ASSERT_EQ(*a,1);
	free(a);
	a = (int*)list_removetail((LIST*)ltq);
	ASSERT_EQ(*a,10);
	free(a);
	ASSERT_EQ(8,list_count((LIST*)ltq));
	a = (int*)malloc(sizeof(int));
	*a = 5;
	ASSERT_EQ(SUCCESS,list_isexist((LIST*)ltq,a,compare));
	free(a);
	a = (int*)malloc(sizeof(int));
	*a = 6;
	int *b = (int*)list_removedata((LIST*)ltq,a,compare);
	ASSERT_EQ(6,*b);
	free(a);
	free(b);
	list_removeall((LIST*)ltq,free);
}

/*
TEST(test_threadpool,testinit)
{
	THREAD_POOL * thpool = threadpool_init(10);
	//ASSERT_NE((THREAD_POOL*)NULL,thpool);
	sleep(1);
	threadpool_destroy(thpool);
	
	
	while(1)
	{
	}
	
	
}
*/

int sort_compare(const void *a,const void *b)
{
	int * tmp1 = (int *)a;
	int *tmp2 =(int *)b;
	return *tmp1-*tmp2;
}




TEST(test_sort,testisort)
{

	int a[10] = {3,5,1,9,4,2,8,6,7,10};
	isort(a,10,sizeof(int),sort_compare);
	for(int i = 0; i<10; i++)
		ASSERT_EQ(i+1,a[i]);
}

TEST(test_sort,testisortji)
{
	int a[9] = {1,9,2,8,3,7,4,6,5};
	isort(a,9,sizeof(int),sort_compare);
	for(int i=0;i<9;i++)
		ASSERT_EQ(i+1,a[i]);
}

TEST(test_sort,testisortrand)
{
	srand(time(NULL));
	for(int times = 0;times<100000;times++)
	{
		int size = rand()%10;
		int *a = (int*)malloc(sizeof(int)*size);

		for(int i=0;i<size;i++)
		{
			a[i] = rand()%10;
		}

		//printf("before sort:\n");
		for(int i=0;i<size;i++)
		{
		//	printf("%d,",a[i]);
		}
		//printf("\n");
		isort(a,size,sizeof(int),sort_compare);
		//printf("after sort:\n");
		for(int i=0;i<size;i++)
		{
		//	printf("%d,",a[i]);
		}
		//printf("\n");
		for(int i=0;i<size-1;i++)
		{
			ASSERT_LE(a[i],a[i+1]);
		}
		free(a);
	}
}

TEST(test_sort,testssortsimple)
{
	int a[10] = {1,10,2,9,3,8,4,7,5,6};
	ssort(a,10,sizeof(int),sort_compare);

	for(int i=0;i<10;i++)
	{
		ASSERT_EQ(i+1,a[i]);
		//printf("%d,",a[i]);
	}
	//printf("\n");
}

TEST(test_sort,testsortrand)
{
	int a[10] = {0};

	for(int i=0;i<10;i++)
	{
		a[i]=rand()%10;
	}

	//printf("before sort\n");

	for(int i=0;i<10;i++)
	{
		//printf("%d,",a[i]);
	}
	//printf("\n");

	ssort(a,10,sizeof(int),sort_compare);

	//printf("after sort\n");

	for(int i=0;i<10;i++)
	{
		//printf("%d,",a[i]);
	}
	//printf("\n");

	for(int i=0;i<9;i++)
	{
		ASSERT_LE(a[i],a[i+1]);
	}
}

TEST(test_sort,testssortrand1)
{
	srand(time(NULL));
	for(int times = 0;times<100000;times++)
	{
		int size = rand()%10;
		int *a = (int*)malloc(sizeof(int)*size);

		for(int i=0;i<size;i++)
		{
			a[i] = rand()%10;
		}

		//printf("before sort:\n");
		for(int i=0;i<size;i++)
		{
			//printf("%d,",a[i]);
		}
		//printf("\n");
		ssort(a,size,sizeof(int),sort_compare);
		//printf("after sort:\n");
		for(int i=0;i<size;i++)
		{
			//printf("%d,",a[i]);
		}
		//printf("\n");
		for(int i=0;i<size-1;i++)
		{
			ASSERT_LE(a[i],a[i+1]);
		}
		free(a);
	}
}

TEST(test_sort,shellsortsimple)
{
	int a[10] = {8,3,6,9,4,10,2,5,1,7};
	shellsort(a,10,sizeof(int),sort_compare);
	/*
	for(int i=0;i<10;i++)
		printf("%d,",a[i]);
	printf("\n");
	*/
	for(int i=0;i<10;i++)
		ASSERT_EQ(i+1,a[i]);
}


TEST(test_sort,testshellsortrand)
{
	int a[10] = {0};

	for(int i=0;i<10;i++)
	{
		a[i]=rand()%10;
	}

	//printf("before sort\n");

	for(int i=0;i<10;i++)
	{
	//	printf("%d,",a[i]);
	}
	//printf("\n");

	shellsort(a,10,sizeof(int),sort_compare);

	//printf("after sort\n");

	for(int i=0;i<10;i++)
	{
		//printf("%d,",a[i]);
	}
	//printf("\n");

	for(int i=0;i<9;i++)
	{
		ASSERT_LE(a[i],a[i+1]);
	}
}



TEST(test_sort,testshellsortrand1)
{
	srand(time(NULL));
	for(int times = 0;times<100000;times++)
	{
		int size = rand()%20;
		int *a = (int*)malloc(sizeof(int)*size);

		for(int i=0;i<size;i++)
		{
			a[i] = rand()%10;
		}

		//printf("before sort:\n");
		for(int i=0;i<size;i++)
		{
		//	printf("%d,",a[i]);
		}
		//printf("\n");
		shellsort(a,size,sizeof(int),sort_compare);
		//printf("after sort:\n");
		for(int i=0;i<size;i++)
		{
		//	printf("%d,",a[i]);
		}
//		printf("\n");
		for(int i=0;i<size-1;i++)
		{
			ASSERT_LE(a[i],a[i+1]);
		}
		free(a);
	}
}

TEST(test_sort,partitionthreeintrand2)
{
	srand(time(NULL));
	for(int i=0;i<100000;i++)
	{
		int size = ((unsigned)(rand()))%10;
		int *a = (int*)malloc(sizeof(int)*size);

		//printf("before partition\n");
		for(int j=0;j<size;j++)
		{
			a[j] = rand()%5;
		//	printf("%d,",a[j]);
		}
	//	printf("\n");

		int m;
		int n;
		partition(a,size,sizeof(int),sort_compare,&n,&m);

		//printf("afterpartition\n");
		//printf("n:%d,m:%d\n",n,m);
		for(int i=0;i<size;i++)
		{
		//	printf("%d,",a[i]);
		}
		//printf("\n");
		for(int i=0;i<size;i++)
		{
			if(i<=n)
			{
				ASSERT_LT(a[i],a[n+1]);
			}
			else if(i>n && i<m)
			{
				ASSERT_EQ(a[i],a[n+1]);
			}
			else
			{
				ASSERT_LT(a[n+1],a[i]);
			}
		}
		free(a);
	}
}

TEST(test_sort,testqqsortthree)
{
	srand(time(NULL));
	for(int times = 0;times<1000;times++)
	{
		int size = rand()%1000;
		int *a = (int*)malloc(sizeof(int)*size);

		for(int i=0;i<size;i++)
		{
			a[i] = rand()%10;
		}

		//printf("before sort:\n");
	//	for(int i=0;i<size;i++)
	//	{
		//	printf("%d,",a[i]);
	//	}
		//printf("\n");
		qqsort(a,size,sizeof(int),sort_compare);
		//printf("after sort:\n");
	//	for(int i=0;i<size;i++)
	//	{
		//	printf("%d,",a[i]);
	//	}
		//printf("\n");
		for(int i=0;i<size-1;i++)
		{
			ASSERT_LE(a[i],a[i+1]);
		}
		free(a);
	}
}

/*
TEST(test_sort,merge)
{
	int a[] = {1,3,5,7,2,4,6,8};
	merge_int(a,8,3);
	for(int i=0;i<=7;i++)
		ASSERT_EQ(a[i],i+1);
}


TEST(test_sort,mergerand)
{
	srand(time(NULL));
	for(int i=0;i<100000;i++)
	{
		int size1 = rand()%10;
		int size2 = rand()%10;
		int *a = (int*)malloc(sizeof(int)*size1);
		int *b = (int*)malloc(sizeof(int)*size2);
		int *c = (int*)malloc(sizeof(int)*(size1+size2));

		for(int i=0;i<size1;i++)
			a[i] = rand()%10;
		for(int j=0;j<size2;j++)
			b[j] = rand()%10;

		isort(a,size1,sizeof(int),sort_compare);
		isort(b,size2,sizeof(int),sort_compare);
		memcpy(c,a,sizeof(int)*size1);
		memcpy(c+size1,b,sizeof(int)*size2);
		merge_int(c,size2+size1,size1-1);
	//	printf("after merge\n");
		for(int i=0;i<size1+size2-1;i++)
			ASSERT_LE(c[i],c[i+1]);
			//printf("%d,",c[i]);
		//printf("\n");
		free(a);
		free(b);
		free(c);
	}
}
*/


/*
TEST(test_sort,mergesortint)
{
	int a[] = {1,3,5,7,2,4,6,8};
	msort_int(a,8);

	for(int i=0;i<7;i++)
	{
	//	printf("%d\n",a[i]);
		ASSERT_LE(a[i],a[i+1]);
	}
}
*/

TEST(test_sort,mergesort)
{
	int a[] = {1,3,5,7,2,4,6};
	msort(a,7,sizeof(int),sort_compare);

	for(int i=0;i<6;i++)
	{
	//	printf("%d\n",a[i]);
		ASSERT_LE(a[i],a[i+1]);
	}
}

TEST(test_sort,mergesortrand)
{
	srand(time(NULL));
	for(int times = 0;times<1000;times++)
	{
		int size = rand()%1000;
		int *a = (int*)malloc(sizeof(int)*size);

		for(int i=0;i<size;i++)
		{
			a[i] = rand()%10;
		}

		/*
		printf("before sort:\n");
			for(int i=0;i<size;i++)
			{
			printf("%d,",a[i]);
			}
		printf("\n");
		*/
		msort(a,size,sizeof(int),sort_compare);
		/*
		printf("after sort:\n");
			for(int i=0;i<size;i++)
			{
			printf("%d,",a[i]);
			}
		printf("\n");
		*/
		for(int i=0;i<size-1;i++)
		{
			ASSERT_LE(a[i],a[i+1]);
		}
		free(a);
	}
}



/*
TEST(test_sort,comeach)
{
	int a = 10;
	int b = 20;
	comeach(&a,&b,sizeof(int),sort_compare);
	ASSERT_EQ(a,10);
	ASSERT_EQ(b,20);
	a = 20;
	b = 10;
	comeach(&a,&b,sizeof(int),sort_compare);
	ASSERT_EQ(10,a);
	ASSERT_EQ(20,b);
}
*/

/*
TEST(test_sort,testqqsortthreeint)
{
	srand(time(NULL));
	for(int times = 0;times<10000;times++)
	{
		int size = rand()%1000;
		int *a = (int*)malloc(sizeof(int)*size);

		for(int i=0;i<size;i++)
		{
			a[i] = rand()%5;
		}

		//printf("before sort:\n");
		for(int i=0;i<size;i++)
		{
		//	printf("%d,",a[i]);
		}
		//printf("\n");
		qqsort_three_int(a,size);
		//printf("after sort:\n");
		for(int i=0;i<size;i++)
		{
		//	printf("%d,",a[i]);
		}
		//printf("\n");
		for(int i=0;i<size-1;i++)
		{
			ASSERT_LE(a[i],a[i+1]);
		}
		free(a);
	}
}
*/

/*
TEST(test_sort,qqsort_three_int)
{
	int a[10]= {1,10,2,4,6,7,3,9,8,5};
	qqsort_three_int(a,10);

	for(int i=0;i<10;i++)
		printf("%d,",a[i]);
	printf("\n");

	for(int i=0;i<10;i++)
		ASSERT_EQ(i+1,a[i]);
}
*/
/*
TEST(test_sort,partitionthreeintrand1)
{
	srand(time(NULL));
	for(int i=0;i<100000;i++)
	{
		int size = ((unsigned)(rand()))%10;
		int *a = (int*)malloc(sizeof(int)*size);

	//	printf("before partition\n");
		for(int j=0;j<size;j++)
		{
			a[j] = rand()%5;
	//		printf("%d,",a[j]);
		}
	//	printf("\n");

		int m;
		int n;
		partition_three_int(a,size,&n,&m);

	//	printf("afterpartition\n");
	//	printf("n:%d,m:%d\n",n,m);
		for(int i=0;i<size;i++)
		{
			//printf("%d,",a[i]);
		}
		//printf("\n");
		for(int i=0;i<size;i++)
		{
			if(i<=n)
			{
				ASSERT_LT(a[i],a[n+1]);
			}
			else if(i>n && i<m)
			{
				ASSERT_EQ(a[i],a[n+1]);
			}
			else
			{
				ASSERT_LT(a[n+1],a[i]);
			}
		}
		free(a);
	}
}
*/

/*
TEST(test_sort,threepartitionproblem)
{
	int a[10] = {1,9,2,4,8,10,5,6,3,7};
	int n,m;
	partition_three_int(a,10,&n,&m);
	for(int i=0;i<10;i++)
	{
		printf("%d,",a[i]);
	}
	printf("\n");

	for(int i=0;i<10;i++)
	{
		if(i<=n)
		{
			ASSERT_LT(a[i],a[n+1]);
		}
		else if(i>n && i<m)
		{
			ASSERT_EQ(a[i],a[n+1]);
		}
		else
		{
			ASSERT_LT(a[n+1],a[i]);
		}
	}
}
*/

/*
TEST(test_sort,partitionthree)
{
	int a[10]={1,3,2,4,2,5,2,8,2,4};
	int i;
	int k;
	k = partition_three_int(a,10,&i);
	//ASSERT_EQ(k,0);
	//ASSERT_EQ(i,6);
	for(int j =0;j<10;j++)
		printf("%d,",a[j]);
	printf("\n");
}
*/

/*
TEST(test_sort,partitionthreerand)
{
	int a[7] = {3,1,2,1,3,2,1};
	for(int i=0;i<7;i++)
	{
		//a[i] = rand()%5;
		//printf("%d,",a[i]);
	}
	//printf("\n");
	int m;
	int n;
	partition_three_int(a,7,&n,&m);

	//printf("n:%d,m:%d\n",n,m);
	for(int i=0;i<7;i++)
	{
	//	printf("%d,",a[i]);
	}
	//printf("\n");
	for(int i=0;i<7;i++)
	{
		if(i<=n)
		{
			ASSERT_LT(a[i],a[n+1]);
		}
		else if(i>n && i<m)
		{
			ASSERT_EQ(a[i],a[n+1]);
		}
		else
		{
			ASSERT_LT(a[n+1],a[i]);
		}
	}
}
*/
/*
TEST(test_sort,testqqsortsample1)
{
	int a[10]={1,10,2,3,8,5,4,9,6,7};
	qqsort(a,10,sizeof(int),sort_compare);
	for(int i=0;i<10;i++)
	{
		ASSERT_EQ(i+1,a[i]);
	}
	
}
*/
